package 简单算法;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: 胡成
 * @Version: 0.0.1V
 * @Date: 2019-05-21
 * @Description: 给定一个整数数组，找到一个具有最小和的子数组。返回其最小和。
 * <p>
 * 样例
 * 样例 1
 * <p>
 * 输入：[1, -1, -2, 1]
 * 输出：-3
 * 样例 2
 * <p>
 * 输入：[1, -1, -2, 1, -4]
 * 输出：-6
 * 注意事项
 * 子数组最少包含一个数字
 **/
public class 最小子数组 {
    public static void main(String[] args) {
        最小子数组 s = new 最小子数组();
        List<Integer> nums = new ArrayList<>();
        nums.add(1);
        nums.add(-1);
        nums.add(-2);
        nums.add(1);
        System.out.println(s.minSubArray(nums));
    }

    public int minSubArray(List<Integer> nums) {
        // write your code here
        int min = Integer.MAX_VALUE, sum = 0;
        for (int i = 0; i < nums.size(); i++) {
            sum += nums.get(i);
            if (sum < min) {
                min = sum;
            }
            if (sum > 0) {
                sum = 0;
            }
        }
        return min;
    }
}
